package org.myy.learn.hot.二叉树.有序数据转为二叉排序树;

import lombok.extern.slf4j.Slf4j;

import java.util.LinkedList;
import java.util.Queue;

@Slf4j
class Solution {

    //ToDo 二叉搜索树的中序遍历是升序序列。  >>>找到中点+答案不唯一

    public static TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    public static TreeNode helper(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        // 总是选择中间位置左边的数字作为根节点
        int mid = (left + right) / 2;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid - 1);
        root.right = helper(nums, mid + 1, right);
        return root;
    }

    private static TreeNode buildTree(Integer[] values){
        if (values == null || values.length == 0){return null;}

        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int index = 1;
        while (!queue.isEmpty() && index < values.length){
            TreeNode node = queue.poll();

            //左节点
            if(index < values.length && values[index] != null){
                node.left = new TreeNode(values[index]);
                queue.offer(node.left);
            }
            index++;

            //右节点
            if(index < values.length && values[index] != null){
                node.right = new TreeNode(values[index]);
                queue.offer(node.right);
            }
            index++;

        }
        return root;
    }

    public static void main(String[] args) {
        int[] values = new int[]{-10,-3,0,5,9};
        TreeNode bst = sortedArrayToBST(values);
        log.info("执行结束，二叉排序树={}", bst);
    }
}
